/**
 * @author Burcak Otlu Saritas
 *
 * 
 */

package intervaltree;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import annotate.encode.Commons;
import annotate.intervals.parametric.KeggPathway;


public class IntervalTree {

	IntervalTreeNode root;
	
	
	
	public IntervalTreeNode getRoot() {
		return root;
	}

	public void setRoot(IntervalTreeNode root) {
		this.root = root;
	}
	
	

	public IntervalTree() {
		super();
		root = null;
	}
	
	

	public int maximum(int x, int y, int z){
		
		int max = x;
	
		if (y>max) 
			max = y;
		if (z>max ) 
			max = z;
		
		return max;
	}
	

	
	public int max(IntervalTreeNode node){
		
		int a = Integer.MIN_VALUE;
		int b = Integer.MIN_VALUE;
		
		if (node.getLeft()!=null)
			a= node.getLeft().getMax();
		
		if(node.getRight()!=null)
			b= node.getRight().getMax();
		
		return maximum(node.getHigh(), a, b);
					
	}
	
	
	
//	We change the pointer structure with Rotation  
//	When we do a left rotation on a node x,
//	we assume that its right child y is not null.
//	Left rotation pivots around the link from x to y.
//	It makes the y the new root of the subtree, with x as the new left child of y 
//	and y's left child becomes x's right child
//	burcak: left rotate edilen node x right child'inin y diyelim, left child'i oluyor
	public void intervalTreeLeftRotate(IntervalTree tree, IntervalTreeNode x){
		IntervalTreeNode y = x.getRight();
		
		if(y==null){
			System.out.println("Invalid Left Rotate Operation");
		}
		else {
			x.setRight(y.getLeft());
			if(y.getLeft()!=null){
				y.getLeft().setParent(x);
			}
			y.setParent(x.getParent());
			
			if(x.getParent()==null){
				tree.setRoot(y);
			} else{
				if(x==(x.getParent().getLeft())){
					x.getParent().setLeft(y);
				}else{
					x.getParent().setRight(y);
				}	
			}
			
			y.setLeft(x);
			x.setParent(y);
			
//			update max attributes
			x.setMax(max(x));
			y.setMax(max(y));
				
		}

	}
	
//	burcak: right rotate edilen node x left child'inin y diyelim, right child'i oluyor
	public void intervalTreeRightRotate(IntervalTree tree, IntervalTreeNode x){
		IntervalTreeNode y = x.getLeft();
		
		if(y==null){
			System.out.println("Invalid Right Rotate Operation");
		}
		else {
			x.setLeft(y.getRight());
			if(y.getRight()!=null){
				y.getRight().setParent(x);
			}
			y.setParent(x.getParent());
			
			if(x.getParent()==null){
				tree.setRoot(y);
			} else{
				if(x==(x.getParent().getLeft())){
					x.getParent().setLeft(y);
				}else{
					x.getParent().setRight(y);
				}	
			}
			
			y.setRight(x);
			x.setParent(y);
			
//			update max attributes
			x.setMax(max(x));
			y.setMax(max(y));			
				
		}
	}

	
	public void intervalTreeInsertFixUp(IntervalTree tree, IntervalTreeNode z){
		IntervalTreeNode y;
		
			while(z.getParent()!=null && z.getParent().getColor()=='r'){
				if ((z.getParent().getParent().getLeft()) == z.getParent()){
					y= z.getParent().getParent().getRight();
					if (y!=null && y.getColor()=='r'){
						z.getParent().setColor('b'); 				//Case1
						y.setColor('b');             				//Case1
						z.getParent().getParent().setColor('r'); 	//Case1
						z = z.getParent().getParent(); 				//Case1
					}else if (z==z.getParent().getRight()){
						z = z.getParent();							//Case2
						intervalTreeLeftRotate(tree, z);			//Case2
					}else{
						z.getParent().setColor('b');								//Case3
						z.getParent().getParent().setColor('r');					//Case3 
						intervalTreeRightRotate(tree,z.getParent().getParent()); 	//Case3
					}
				}else{
					y= z.getParent().getParent().getLeft();
					if (y!=null && y.getColor()=='r'){
						z.getParent().setColor('b'); 				//Case1
						y.setColor('b');             				//Case1
						z.getParent().getParent().setColor('r'); 	//Case1
						z = z.getParent().getParent(); 				//Case1
					}else if (z==z.getParent().getLeft()){
						z = z.getParent();							//Case2
						intervalTreeRightRotate(tree, z);			//Case2
					}else{
						z.getParent().setColor('b');								//Case3
						z.getParent().getParent().setColor('r');					//Case3 
						intervalTreeLeftRotate(tree,z.getParent().getParent()); 	//Case3
					}

				}
								
			}
		tree.getRoot().setColor('b');
	}
	
	public void updateMaxAttributes(IntervalTreeNode x,int newlyInsertedNodesMax){
		while(x!=null){
			if (newlyInsertedNodesMax > x.getMax()){
				x.setMax(newlyInsertedNodesMax);
				x = x.getParent();			
			}else{
				break;
			}
		}		
	}
	
	public void  intervalTreeInsert(IntervalTree tree, IntervalTreeNode z){
		IntervalTreeNode y = null;
		IntervalTreeNode x = tree.getRoot();
		
//		This while sets the parent for the new inserted node z
		while(x!=null){
			y = x;
			if (z.getLow()< x.getLow())
				x = x.getLeft();
			else 
				x = x.getRight();
		}
		
		z.setParent(y);
		
//		This part sets whether the new inserted node is the left or right child of parent
		if (y==null){//enters for the first insert
			tree.setRoot(z);
		} else{
			if (z.getLow()<y.getLow()){
				y.setLeft(z);
			}else{
				y.setRight(z);
			}			
		}
		
//		sets the left right color attributes of the new inserted node
		z.setLeft(null);
		z.setRight(null);
		z.setColor('r');
		z.setMax(z.getHigh());
		
		updateMaxAttributes(z.getParent(),z.getMax());
		intervalTreeInsertFixUp(tree,z);
	}
	
	
	public void intervalTreeInfixTraversal(IntervalTreeNode node){
		
		if (node.getLeft()!=null)
			intervalTreeInfixTraversal(node.getLeft());
		
		System.out.println(node.getLow() + "\t"+ node.getHigh() + "\t" + node.getMax());
		
		if (node.getRight()!=null)
			intervalTreeInfixTraversal(node.getRight());
				
	}
	
	
	public void intervalTreeInfixTraversal(IntervalTreeNode node,BufferedWriter bufferedWriter){
		
		if (node.getLeft()!=null)
			intervalTreeInfixTraversal(node.getLeft(),bufferedWriter);
		
		try {
			bufferedWriter.write(node.getLow() + "\t"+ node.getHigh() + "\t" + node.getMax()+ "\n");
			bufferedWriter.flush();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		if (node.getRight()!=null)
			intervalTreeInfixTraversal(node.getRight(),bufferedWriter);
		
				
	}
	
	public void intervalTreeInfixTraversal(IntervalTreeNode node,BufferedWriter bufferedWriter, String type){
		
		if (node.getLeft()!=null)
			intervalTreeInfixTraversal(node.getLeft(),bufferedWriter,type);
		
		try {
			if (Commons.DNASE.equals(type)){
				bufferedWriter.write(node.getChromName()+ "\t" + node.getLow()+"\t"+ node.getHigh() +"\t" + node.getCellLineName()+"\t" + node.getFileName()+"\n");																
			}else if (Commons.TFBS.equals(type)){
				bufferedWriter.write(node.getChromName()+ "\t" + node.getLow()+"\t"+ node.getHigh()+"\t" + node.getTfbsorHistoneName()+"\t" + node.getCellLineName()+"\t" + node.getFileName()+"\n");												
			}else if (Commons.HISTONE.equals(type)){
				bufferedWriter.write(node.getChromName()+ "\t" + node.getLow()+"\t"+ node.getHigh()+"\t" + node.getTfbsorHistoneName()+"\t" + node.getCellLineName()+"\t" + node.getFileName()+"\n");												
			}else if(Commons.UCSC_GENE.equals(type)){
				bufferedWriter.write(node.getChromName()+ "\t" + node.getLow()+"\t"+ node.getHigh()+"\t" + node.getRefSeqGeneName()+ "\t" + node.getGeneEntrezId()+ "\t" + node.getIntervalName()+ "\t" + node.getStrand() + "\t" + node.getGeneHugoSymbol()+ "\n");
//				bufferedWriter.write(refSeqGeneIntervalList.get(j).getChromName()+ "\t" +refSeqGeneIntervalList.get(j).getIntervalStart()+"\t"+ refSeqGeneIntervalList.get(j).getIntervalEnd()+"\t" +refSeqGeneIntervalList.get(j).getRefSeqGeneName()+ "\t" + refSeqGeneIntervalList.get(j).getGeneId()+ "\t" +refSeqGeneIntervalList.get(j).getIntervalName()+ "\t" + refSeqGeneIntervalList.get(j).getStrand() + "\t" + refSeqGeneIntervalList.get(j).getAlternateGeneName()+ "\n");
				
			}
			bufferedWriter.flush();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		if (node.getRight()!=null)
			intervalTreeInfixTraversal(node.getRight(),bufferedWriter,type);
		
				
	}
	
	public boolean overlaps(int low_x, int high_x, int low_y, int high_y ){
		if (( low_x <= high_y) && (low_y <= high_x))
			return true;
		else 
			return false;
	}
	

	
	//Normal
	public void findAllOverlappingIntervals(IntervalTreeNode node, Interval interval){
		if (node!=null){
			if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh())){
					System.out.println(node.getLow() + "\t" + node.getHigh());
			}
			
			
			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findAllOverlappingIntervals(node.getLeft(),interval);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findAllOverlappingIntervals(node.getRight(),interval);	
				
			}
		}		
	}
	
	
	//Search1
	public void findAllOverlappingHistoneIntervals(IntervalTreeNode node, Interval interval, BufferedWriter bufferedWriter){
		if (node!=null){
			if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh())){
				try {
					bufferedWriter.write("histone" + "\t" + node.getChromName().toString()+ "\t"  + node.getLow() + "\t" + node.getHigh() + "\t" +node.getTfbsorHistoneName().toString()+ "\t" + node.getCellLineName().toString() + "\t" + node.getFileName().toString() +"\n");
					bufferedWriter.flush();
					
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}					
			}
			
			
			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findAllOverlappingHistoneIntervals(node.getLeft(),interval,bufferedWriter);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findAllOverlappingHistoneIntervals(node.getRight(),interval,bufferedWriter);	
				
			}
		}		
	}
	


	//Search2
	public void findAllOverlappingHistoneIntervals(IntervalTreeNode node, Interval interval, String chromName, Map<String,BufferedWriter> bufferedWriterHashMap, Map<String,Integer> histoneNameHashMap){
		FileWriter fileWriter = null;
		BufferedWriter bufferedWriter = null;
		Integer count;

		if (node!=null){
			if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh()) && histoneNameHashMap.containsKey(node.getTfbsorHistoneName())){
				try {			
					
					bufferedWriter = bufferedWriterHashMap.get(node.getTfbsorHistoneName());
					count = histoneNameHashMap.get(node.getTfbsorHistoneName());

					if (bufferedWriter==null){						
						fileWriter = new FileWriter(Commons.ANNOTATE_INTERVALS_USING_INTERVAL_TREE_OUTPUT_FILE_PATH_FOR_HISTONE +"_" + node.getTfbsorHistoneName() + ".txt");
						bufferedWriter = new BufferedWriter(fileWriter);
						bufferedWriterHashMap.put(node.getTfbsorHistoneName(),bufferedWriter);
					}
										
					bufferedWriter.write("Searched for" + "\t" + chromName + "\t" + interval.getLow() + "\t" + interval.getHigh() + "\t" + "histone" + "\t" + node.getChromName()+ "\t"  + node.getLow() + "\t" + node.getHigh() + "\t" + node.getTfbsorHistoneName()+ "\t" + String.valueOf(node.getCellLineName()) + "\t" + node.getFileName() +"\n");
					bufferedWriter.flush();
					
					count++;
					histoneNameHashMap.put(node.getTfbsorHistoneName(), count);

				} catch (IOException e) {
					e.printStackTrace();
				}					
			}
			
			
			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findAllOverlappingHistoneIntervals(node.getLeft(),interval,chromName,bufferedWriterHashMap, histoneNameHashMap);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findAllOverlappingHistoneIntervals(node.getRight(),interval,chromName,bufferedWriterHashMap,histoneNameHashMap);	
				
			}
		}		
	}

	
	//Search for the first overlapping interval
	public void findFirstOverlappingHistoneInterval(IntervalTreeNode node, Interval interval, String chromName, Map<String,BufferedWriter> bufferedWriterHashMap, Map<String,Integer> histoneNameHashMap){
		FileWriter fileWriter = null;
		BufferedWriter bufferedWriter = null;
		Integer count;

		if (node!=null){
			if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh()) && histoneNameHashMap.containsKey(node.getTfbsorHistoneName())){
				try {			
					
					bufferedWriter = bufferedWriterHashMap.get(node.getTfbsorHistoneName());
					count = histoneNameHashMap.get(node.getTfbsorHistoneName());

					if (bufferedWriter==null){						
						fileWriter = new FileWriter(Commons.ANNOTATE_INTERVALS_USING_INTERVAL_TREE_OUTPUT_FILE_PATH_FOR_HISTONE +"_" + node.getTfbsorHistoneName() + ".txt");
						bufferedWriter = new BufferedWriter(fileWriter);
						bufferedWriterHashMap.put(node.getTfbsorHistoneName(),bufferedWriter);
					}
										
					bufferedWriter.write("Searched for" + "\t" + chromName + "\t" + interval.getLow() + "\t" + interval.getHigh() + "\t" + "histone" + "\t" + node.getChromName()+ "\t"  + node.getLow() + "\t" + node.getHigh() + "\t" + node.getTfbsorHistoneName()+ "\t" + String.valueOf(node.getCellLineName()) + "\t" + node.getFileName() +"\n");
					bufferedWriter.flush();
					
					count++;
					histoneNameHashMap.put(node.getTfbsorHistoneName(), count);
					return;

				} catch (IOException e) {
					e.printStackTrace();
				}					
			}
			
			
			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findFirstOverlappingHistoneInterval(node.getLeft(),interval,chromName,bufferedWriterHashMap, histoneNameHashMap);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findFirstOverlappingHistoneInterval(node.getRight(),interval,chromName,bufferedWriterHashMap,histoneNameHashMap);	
				
			}
		}		
	}
	
	

	//Search2
	public void findAllOverlappingTfbsIntervals(IntervalTreeNode node, Interval interval, String chromName, Map<String,BufferedWriter> bufferedWriterHashMap, Map<String,Integer> tfbsNameHashMap){
		FileWriter fileWriter = null;
		BufferedWriter bufferedWriter = null;
		Integer count;

		if (node!=null){
			if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh()) && tfbsNameHashMap.containsKey(node.getTfbsorHistoneName())){
				try {
										
					bufferedWriter = bufferedWriterHashMap.get(node.getTfbsorHistoneName());
					count = tfbsNameHashMap.get(node.getTfbsorHistoneName());

					if (bufferedWriter==null){						
						fileWriter = new FileWriter(Commons.ANNOTATE_INTERVALS_USING_INTERVAL_TREE_OUTPUT_FILE_PATH_FOR_TFBS +"_" + node.getTfbsorHistoneName() + ".txt");
						bufferedWriter = new BufferedWriter(fileWriter);
						bufferedWriterHashMap.put(node.getTfbsorHistoneName(),bufferedWriter);
					}
					
					bufferedWriter.write("Searched for" + "\t" + chromName + "\t" + interval.getLow() + "\t" + interval.getHigh() +"\t" + "tfbs" + "\t" + node.getChromName()+ "\t"  + node.getLow() + "\t" + node.getHigh() + "\t" + node.getTfbsorHistoneName()+ "\t" + node.getCellLineName() + "\t" + node.getFileName() +"\n");
					bufferedWriter.flush();
					
					count++;
					tfbsNameHashMap.put(node.getTfbsorHistoneName(), count);

				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}					
			}
			
			
			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findAllOverlappingTfbsIntervals(node.getLeft(),interval,chromName, bufferedWriterHashMap,tfbsNameHashMap);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findAllOverlappingTfbsIntervals(node.getRight(),interval,chromName, bufferedWriterHashMap,tfbsNameHashMap);	
				
			}
		}		
	}


	//Search for the first overlapping interval
	public void findFirstOverlappingTfbsInterval(IntervalTreeNode node, Interval interval, String chromName, Map<String,BufferedWriter> bufferedWriterHashMap, Map<String,Integer> tfbsNameHashMap){
		FileWriter fileWriter = null;
		BufferedWriter bufferedWriter = null;
		Integer count;

		if (node!=null){
			if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh()) && tfbsNameHashMap.containsKey(node.getTfbsorHistoneName())){
				try {
										
					bufferedWriter = bufferedWriterHashMap.get(node.getTfbsorHistoneName());
					count = tfbsNameHashMap.get(node.getTfbsorHistoneName());

					if (bufferedWriter==null){						
						fileWriter = new FileWriter(Commons.ANNOTATE_INTERVALS_USING_INTERVAL_TREE_OUTPUT_FILE_PATH_FOR_TFBS +"_" + node.getTfbsorHistoneName() + ".txt");
						bufferedWriter = new BufferedWriter(fileWriter);
						bufferedWriterHashMap.put(node.getTfbsorHistoneName(),bufferedWriter);
					}
					
					bufferedWriter.write("Searched for" + "\t" + chromName + "\t" + interval.getLow() + "\t" + interval.getHigh() +"\t" + "tfbs" + "\t" + node.getChromName()+ "\t"  + node.getLow() + "\t" + node.getHigh() + "\t" + node.getTfbsorHistoneName()+ "\t" + node.getCellLineName() + "\t" + node.getFileName() +"\n");
					bufferedWriter.flush();
					
					count++;
					tfbsNameHashMap.put(node.getTfbsorHistoneName(), count);
					return;

				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}					
			}
			
			
			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findFirstOverlappingTfbsInterval(node.getLeft(),interval,chromName, bufferedWriterHashMap,tfbsNameHashMap);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findFirstOverlappingTfbsInterval(node.getRight(),interval,chromName, bufferedWriterHashMap,tfbsNameHashMap);	
				
			}
		}		
	}

	
	//Search1
	public void findAllOverlappingTfbsIntervals(IntervalTreeNode node, Interval interval, BufferedWriter bufferedWriter){
		if (node!=null){
			if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh())){
				try {
					bufferedWriter.write("tfbs" + "\t" + node.getChromName().toString()+ "\t"  + node.getLow() + "\t" + node.getHigh() + "\t" +node.getTfbsorHistoneName().toString()+ "\t" + node.getCellLineName().toString() + "\t" + node.getFileName().toString() +"\n");
					bufferedWriter.flush();
					
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}					
			}
			
			
			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findAllOverlappingTfbsIntervals(node.getLeft(),interval,bufferedWriter);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findAllOverlappingTfbsIntervals(node.getRight(),interval,bufferedWriter);	
				
			}
		}		
	}
	
	//Search1
	public void findAllOverlappingDnaseIntervals(IntervalTreeNode node, Interval interval, BufferedWriter bufferedWriter){
		if (node!=null){
			if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh())){
				try {
					bufferedWriter.write("dnase" + "\t" + node.getChromName().toString()+ "\t"  + node.getLow() + "\t" + node.getHigh() + "\t" + node.getCellLineName().toString() + "\t" + node.getFileName().toString() +"\n");
					bufferedWriter.flush();
					
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}					
			}
			
			
			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findAllOverlappingDnaseIntervals(node.getLeft(),interval,bufferedWriter);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findAllOverlappingDnaseIntervals(node.getRight(),interval,bufferedWriter);	
				
			}
		}					
	}

	

	//Search2
	public void findAllOverlappingDnaseIntervals(IntervalTreeNode node, Interval interval, String chromName, Map<String,BufferedWriter> bufferedWriterHashMap, Map<String,Integer> dnaseCellLineNameHashMap){
		FileWriter fileWriter = null;
		BufferedWriter bufferedWriter = null;
		Integer count;
		
		if (node!=null){
			if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh()) && dnaseCellLineNameHashMap.containsKey(node.getCellLineName())){
				try {
					
					bufferedWriter = bufferedWriterHashMap.get(node.getCellLineName());
					count = dnaseCellLineNameHashMap.get(node.getCellLineName());
					
					if (bufferedWriter==null){
						fileWriter = new FileWriter(Commons.ANNOTATE_INTERVALS_USING_INTERVAL_TREE_OUTPUT_FILE_PATH_FOR_DNASE +"_" + node.getCellLineName() + ".txt");
						bufferedWriter = new BufferedWriter(fileWriter);
						bufferedWriterHashMap.put(node.getCellLineName(),bufferedWriter);
					}										
					
					bufferedWriter.write("Searched for" + "\t" + chromName + "\t" + interval.getLow() + "\t" + interval.getHigh()+ "\t" + "dnase" + "\t" + node.getChromName()+ "\t"  + node.getLow() + "\t" + node.getHigh() + "\t" + node.getCellLineName() + "\t" + node.getFileName() +"\n");
					bufferedWriter.flush();	
					
					count++;
					dnaseCellLineNameHashMap.put(node.getCellLineName(), count);
					
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}					
			}
			
			
			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findAllOverlappingDnaseIntervals(node.getLeft(),interval,chromName,bufferedWriterHashMap,dnaseCellLineNameHashMap);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findAllOverlappingDnaseIntervals(node.getRight(),interval,chromName,bufferedWriterHashMap,dnaseCellLineNameHashMap);	
				
			}
		}					
	}

	//Search for the first overlapping interval
	public void findFirstOverlappingDnaseInterval(IntervalTreeNode node, Interval interval, String chromName, Map<String,BufferedWriter> bufferedWriterHashMap, Map<String,Integer> dnaseCellLineNameHashMap){
		FileWriter fileWriter = null;
		BufferedWriter bufferedWriter = null;
		Integer count;
		
		if (node!=null){
			if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh()) && dnaseCellLineNameHashMap.containsKey(node.getCellLineName())){
				try {
					
					bufferedWriter = bufferedWriterHashMap.get(node.getCellLineName());
					count = dnaseCellLineNameHashMap.get(node.getCellLineName());
					
					if (bufferedWriter==null){
						fileWriter = new FileWriter(Commons.ANNOTATE_INTERVALS_USING_INTERVAL_TREE_OUTPUT_FILE_PATH_FOR_DNASE +"_" + node.getCellLineName() + ".txt");
						bufferedWriter = new BufferedWriter(fileWriter);
						bufferedWriterHashMap.put(node.getCellLineName(),bufferedWriter);
					}										
					
					bufferedWriter.write("Searched for" + "\t" + chromName + "\t" + interval.getLow() + "\t" + interval.getHigh()+ "\t" + "dnase" + "\t" + node.getChromName()+ "\t"  + node.getLow() + "\t" + node.getHigh() + "\t" + node.getCellLineName() + "\t" + node.getFileName() +"\n");
					bufferedWriter.flush();	
					
					count++;
					dnaseCellLineNameHashMap.put(node.getCellLineName(), count);
					return;
					
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}					
			}
			
			
			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findFirstOverlappingDnaseInterval(node.getLeft(),interval,chromName,bufferedWriterHashMap,dnaseCellLineNameHashMap);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findFirstOverlappingDnaseInterval(node.getRight(),interval,chromName,bufferedWriterHashMap,dnaseCellLineNameHashMap);	
				
			}
		}					
	}
	

	//overload for keggPathway Search2
	public void findAllOverlappingUcscRefSeqGenesIntervals(IntervalTreeNode node, Interval interval, String chromName, Map<String,BufferedWriter> bufferedWriterHashMap, Map<String,Integer> keggPathwayNameHashMap, List<KeggPathway> keggPathwayList, List<String> nameorIdList, String type){
		FileWriter fileWriter = null;
		BufferedWriter bufferedWriter = null;
		
		String keggPathwayName = null;
		Integer count ;
		if (node!=null){
			
			if (Commons.NCBI_GENE_ID.equals(type)){
				if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh()) && nameorIdList.contains(node.getGeneEntrezId().toString())){
					try {
						
						for(int i = 0; i<keggPathwayList.size(); i++){
							if (keggPathwayList.get(i).getNcbiGeneIdList().contains(node.getGeneEntrezId().toString())){
								
								keggPathwayName = keggPathwayList.get(i).getKeggPathwayName();
								count = keggPathwayNameHashMap.get(keggPathwayName);
								
								bufferedWriter = bufferedWriterHashMap.get(keggPathwayName);
								
								if (bufferedWriter == null){
									fileWriter = new FileWriter(Commons.ANNOTATE_INTERVALS_USING_INTERVAL_TREE_OUTPUT_FILE_PATH_FOR_KEGG_PATHWAY +"_" + keggPathwayName + ".txt");
									bufferedWriter = new BufferedWriter(fileWriter);
									bufferedWriterHashMap.put(keggPathwayName, bufferedWriter);
									
								}
								
								bufferedWriter.write("Searched for" + "\t" + chromName + "\t" + interval.getLow() + "\t" + interval.getHigh() + "\t" + "ucscRefSeqGene" + "\t" + node.getChromName()+ "\t" +  node.getLow() + "\t" + node.getHigh() + "\t" + node.getRefSeqGeneName()+ "\t" + node.getIntervalName() + "\t" + node.getGeneHugoSymbol()+ "\t"+ node.getGeneEntrezId() +"\n");
								bufferedWriter.flush();	
								
								count++;
								keggPathwayNameHashMap.put(keggPathwayName, count);
							}
							
						}
						
										
					} catch (IOException e) {
						e.printStackTrace();
					}					
				}	
			}
				
			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findAllOverlappingUcscRefSeqGenesIntervals(node.getLeft(),interval,chromName,bufferedWriterHashMap, keggPathwayNameHashMap,keggPathwayList,nameorIdList,type);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findAllOverlappingUcscRefSeqGenesIntervals(node.getRight(),interval,chromName,bufferedWriterHashMap, keggPathwayNameHashMap,keggPathwayList,nameorIdList,type);	
				
			}
		}				
	}
	
	
	

	
	
	

//Search2
public void findAllOverlappingUcscRefSeqGenesIntervals(IntervalTreeNode node, Interval interval, String chromName, Map<String,BufferedWriter> bufferedWriterHashMap, Map<String,Integer> nameorIdHashMap, String type){
	FileWriter fileWriter = null;
	BufferedWriter bufferedWriter = null;
	Integer count ;
	
	try {
		
		if (node!=null){
			
			if (Commons.NCBI_GENE_ID.equals(type)){
				if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh()) && nameorIdHashMap.containsKey(node.getGeneEntrezId().toString())){
						
					bufferedWriter = bufferedWriterHashMap.get(node.getGeneEntrezId().toString());
					count =  nameorIdHashMap.get(node.getGeneEntrezId().toString());
					
					if (bufferedWriter == null){
						fileWriter = new FileWriter(Commons.ANNOTATE_INTERVALS_USING_INTERVAL_TREE_OUTPUT_FILE_PATH_FOR_NCBI_GENE_ID +"_" +String.valueOf(node.getGeneEntrezId()) + ".txt");
						bufferedWriter = new BufferedWriter(fileWriter);
						bufferedWriterHashMap.put(node.getGeneEntrezId().toString(), bufferedWriter);
					
					}							
					
					
					
					bufferedWriter.write("Searched for" + "\t" + chromName + "\t" + interval.getLow() + "\t" + interval.getHigh() + "\t" + "ucscRefSeqGene" + "\t" + node.getChromName()+ "\t" +  node.getLow() + "\t" + node.getHigh() + "\t" + node.getRefSeqGeneName() + "\t" + node.getIntervalName() + "\t" + node.getGeneHugoSymbol()+ "\t"+ node.getGeneEntrezId() +"\n");
					bufferedWriter.flush();					
										
					count++;
					nameorIdHashMap.put(node.getGeneEntrezId().toString(), count);
				}	
			}else if (Commons.NCBI_RNA_NUCLEOTIDE_ACCESSION_VERSION.equals(type)){
				if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh()) &&nameorIdHashMap.containsKey(node.getRefSeqGeneName())){

						bufferedWriter = bufferedWriterHashMap.get(node.getRefSeqGeneName());
						count =  nameorIdHashMap.get(node.getRefSeqGeneName());
						
						if (bufferedWriter == null){
							fileWriter = new FileWriter(Commons.ANNOTATE_INTERVALS_USING_INTERVAL_TREE_OUTPUT_FILE_PATH_FOR_NCBI_RNA +"_" + node.getRefSeqGeneName() + ".txt");
							bufferedWriter = new BufferedWriter(fileWriter);
							bufferedWriterHashMap.put(node.getRefSeqGeneName(), bufferedWriter);							
						}
													
						bufferedWriter.write("Searched for" + "\t" + chromName + "\t" + interval.getLow() + "\t" + interval.getHigh() + "\t" + "ucscRefSeqGene" + "\t" + node.getChromName()+ "\t" +  node.getLow() + "\t" + node.getHigh() + "\t" + node.getRefSeqGeneName() + "\t" + node.getIntervalName() + "\t" + node.getGeneHugoSymbol()+ "\t"+ node.getGeneEntrezId() +"\n");
						bufferedWriter.flush();		
						
						count++;
						nameorIdHashMap.put(node.getRefSeqGeneName(), count);
										
				}	
			}else if(Commons.UCSC_GENE_ALTERNATE_NAME.equals(type)){
				if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh()) && nameorIdHashMap.containsKey(node.getGeneHugoSymbol())){
				
						bufferedWriter = bufferedWriterHashMap.get(node.getGeneHugoSymbol());
						count =  nameorIdHashMap.get(node.getGeneHugoSymbol());
						
						if (bufferedWriter == null){
							fileWriter = new FileWriter(Commons.ANNOTATE_INTERVALS_USING_INTERVAL_TREE_OUTPUT_FILE_PATH_FOR_UCSC_GENE_ALTERNATE_NAME +"_" + node.getGeneHugoSymbol() + ".txt");
							bufferedWriter = new BufferedWriter(fileWriter);
							bufferedWriterHashMap.put(node.getGeneHugoSymbol(), bufferedWriter);							
						}
												
						bufferedWriter.write("Searched for" + "\t" + chromName + "\t" + interval.getLow() + "\t" + interval.getHigh() + "\t" + "ucscRefSeqGene" + "\t" + node.getChromName()+ "\t" +  node.getLow() + "\t" + node.getHigh() + "\t" + node.getRefSeqGeneName()+ "\t" +  node.getIntervalName() + "\t" + node.getGeneHugoSymbol()+ "\t"+ node.getGeneEntrezId() +"\n");
						bufferedWriter.flush();					
						
						count++;
						nameorIdHashMap.put(node.getGeneHugoSymbol(), count);
				}	
			}

			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findAllOverlappingUcscRefSeqGenesIntervals(node.getLeft(),interval,chromName, bufferedWriterHashMap, nameorIdHashMap,type);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findAllOverlappingUcscRefSeqGenesIntervals(node.getRight(),interval,chromName, bufferedWriterHashMap, nameorIdHashMap,type);	
				
			}
		} // If node is not null
					
		
	} catch (IOException e) {
		e.printStackTrace();
	}		
}	






	//Search1
	public void findAllOverlappingUcscRefSeqGenesIntervals(IntervalTreeNode node, Interval interval, BufferedWriter bufferedWriter){
		
		if (node!=null){
			if (overlaps(node.getLow(), node.getHigh(), interval.getLow(), interval.getHigh())){
				try {
					bufferedWriter.write("ucscRefSeqGene" + "\t" + node.getChromName().toString()+ "\t" +  node.getLow() + "\t" + node.getHigh() + "\t" + node.getRefSeqGeneName().toString()+ "\t" + node.getIntervalName().toString() + "\t" + node.getGeneHugoSymbol().toString()+ "\t"+ node.getGeneEntrezId() +"\n");
					bufferedWriter.flush();
					
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}					
			}
			
			
			if((node.getLeft()!=null) && (interval.getLow()<=node.getLeft().getMax())){
				findAllOverlappingUcscRefSeqGenesIntervals(node.getLeft(),interval,bufferedWriter);	
			}
			
			if((node.getRight()!=null) && (interval.getLow()<=node.getRight().getMax()) && (node.getLow()<=interval.getHigh())){
				findAllOverlappingUcscRefSeqGenesIntervals(node.getRight(),interval,bufferedWriter);	
				
			}
		}				
	}
	
	public void printOverlappingIntervalsList(List<IntervalTreeNode> list){
		Iterator<IntervalTreeNode> itr = list.iterator();
		
		while(itr.hasNext()){
			IntervalTreeNode  node =(IntervalTreeNode) itr.next();			
			System.out.println(node.getLow() + "\t" + node.getHigh());
			
		}
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		IntervalTree tree = new IntervalTree();
		List<IntervalTreeNode> resultList ;

		IntervalTreeNode node1 = new IntervalTreeNode(10,15);
		IntervalTreeNode node_1 = new IntervalTreeNode(10,15);
		IntervalTreeNode node_2 = new IntervalTreeNode(10,15);
		IntervalTreeNode node2 = new IntervalTreeNode(5,40);
		IntervalTreeNode node3 = new IntervalTreeNode(15,60);
		IntervalTreeNode node4 = new IntervalTreeNode(2,80);
		IntervalTreeNode node5 = new IntervalTreeNode(1,100);
		IntervalTreeNode node6 = new IntervalTreeNode(3,150);
		IntervalTreeNode node7 = new IntervalTreeNode(6,36);
		IntervalTreeNode node8 = new IntervalTreeNode(7,77);
		IntervalTreeNode node9 = new IntervalTreeNode(8,200);
		IntervalTreeNode node10 = new IntervalTreeNode(4,20);
		IntervalTreeNode node11 = new IntervalTreeNode(40,140);
		IntervalTreeNode node12 = new IntervalTreeNode(60,120);
		IntervalTreeNode node13 = new IntervalTreeNode(50,150);
		IntervalTreeNode node14 = new IntervalTreeNode(55,90);
		
		
		tree.intervalTreeInsert(tree, node1);
		tree.intervalTreeInsert(tree, node_1);
		tree.intervalTreeInsert(tree, node_2);
		tree.intervalTreeInsert(tree, node2);
		tree.intervalTreeInsert(tree, node3);
		tree.intervalTreeInsert(tree, node4);
		tree.intervalTreeInsert(tree, node5);
		tree.intervalTreeInsert(tree, node6);
		tree.intervalTreeInsert(tree, node7);
		tree.intervalTreeInsert(tree, node8);
		tree.intervalTreeInsert(tree, node9);
		tree.intervalTreeInsert(tree, node10);
		tree.intervalTreeInsert(tree, node11);
		tree.intervalTreeInsert(tree, node12);
		tree.intervalTreeInsert(tree, node13);
		tree.intervalTreeInsert(tree, node14);
		
		System.out.println("Interval Tree Infix Traversal");
		tree.intervalTreeInfixTraversal(tree.getRoot());
		
		System.out.println("Overlapping Intervals");
		tree.findAllOverlappingIntervals(tree.getRoot(), new Interval(5,20));
		
//		tree.printOverlappingIntervalsList(resultList);
		
		
		
	}

	
}
